package com.wuxuan.algorithm_homework.bit;

/**
 * 1、一个数组，其中一个数字出现一次，其余出现两次，找出只出现一次的数字。
 * 追问:一个数组，其中一个数字出现一次，其余出现 K 次(K为大于1的奇数)，找出只出现一次的数字。
 * 要求:时间复杂度0(n)，空间复杂度 0(1)
 */
public class BitTest {
    //任何数字和自己异或结果是0，比如 5 ^ 5 = 0。
    //任何数字和0异或结果还是它自己，比如 5 ^ 0 = 5。
    //所以，如果我们把所有数字都异或一遍，那些成对的数字都会变成0，最后剩下的就是那个只出现一次的数字了。
    //如下：

    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    //追问：如果一个数字出现一次，其余出现K次（K是大于1的奇数），怎么办？
    //这时候，异或运算就不够用了，因为K次出现的数字异或结果不一定是0。我们需要用另一种方法。

    //第一步：
    // 统计每一位上1的个数
    //我们把每个数字都拆成二进制，然后统计每一位上1的个数。比如数字5（二进制是101），第二位和第四位是1。

    //第二步：
    // 判断哪一位上1的个数是K的倍数加1
    //如果某一位上1的个数是K的倍数加1，说明那个只出现一次的数字在这一位上是1。

    public int singleNumber(int[] nums, int k) {
        int result = 0;
        //整数由32位二进制表示
        int numDigits = 32;
        for (int i = 0; i < numDigits; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                //统计数组中所有元素，从右向左数第i位二进制位上1的个数，>>为右移操作
                //所以，nums[j] >> i & 1 的意思是：
                //先把 nums[j] 右移 i 位。
                //然后和1做与操作，检查右移后的数字的最后一位是不是1。
                count += (nums[j] >> i & 1);
            }
            if (count % k == 1) {
                //还原只出现一次的数 1 的分布，<<为左移操作
//                result |= (1 << i);
                result = result | (1 << i);
            }
        }
       return result;
    }

    /**
     * 用位运算实现两数加法
     *
     * @param a
     * @param b
     * @return
     */
    public int add(int a, int b) {
        // 思路：
        // 我们发现只有 1 和 1 相加才产生进位，可以用与(&)来计算进位，
        // 而其他三种组合的运算结果都符合 异或 ^ 的运算规则，相同为 0，不同为 1。
        // 因此用位运算来计算两数(a，b)相加可以拆分为两个步骤
        // 1.计算两数无进位加法，得到结果 X
        // 2.计算两数进位，由于进位的“效应"需要在下一位才能实现，需将结果左移，得到结果 Y
        // 若进位 Y为 0，则返回最终的结果 X:
        // 若进位Y不为 0，则要继续计算 X+Y 令a=X,b=Y, 又可以重复利用程序进行两数之和的计算，直到进位为 0，计算完成。
        while (b != 0) {
            //计算进位
            int carry = (a & b) << 1;

            //计算无进位加法(用异或可以表示)
            a = a ^ b;

            //更新进位
            b = carry;
        }
        return a;
    }
}
